package com.mystudy.algorithm.sort;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @program: infoalgorithm
 * @description: 插入排序
 * @author: zhouzhilong
 * @create: 2019-07-30 11:18
 **/
public class InsertionSort {
    /** logger */
    private static final Logger LOGGER = LoggerFactory.getLogger(InsertionSort.class);

    @Test
    public void test() {
        int[] arr = new int[]{4, 1, 9, 5, 1, 9, 5, 6, 6, 9, 2, 15, 21, 96, 34};
        int[] sort = sort(arr);
        LOGGER.debug("sort = [{}]",sort);
    }


    private int[] sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int preIndex = i-1;
            int cur = arr[i];
            while (preIndex >= 0 && arr[preIndex] > cur) {
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }

            arr[preIndex+1] = cur;
        }
        return arr;
    }

}
